package utility;

import model.beans.DirectedGraphBean;
import model.beans.LinkBean;
import model.beans.RouterBean;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import org.apache.log4j.Logger;

/**
 *
 * @author Danon
 */
public abstract class Utils {
    private static final Logger logger = Logger.getLogger(Utils.class);
  
    public static List<LinkBean> 
            Dijkstra(RouterBean v1,
                     RouterBean v2,
                     float minBandwidth
                     ) 
    {
        logger.trace("Starting dijkstra("+ v1 + " and "+ v2 + ") with minBandwidth="+minBandwidth);
        int N = DirectedGraphBean.size();

        // create data structures
        logger.trace("Dijkstra: creating data structures");
        List<LinkBean> circuit = new ArrayList<>();
        Set<Pair<Float, RouterBean>> q = new TreeSet<>(new Comparator<Pair<Float, RouterBean>>() {

            @Override
            public int compare(Pair<Float, RouterBean> o1, Pair<Float, RouterBean> o2) {
                int r = o1.getA().compareTo(o2.getA());
                if(r!=0) return r;
                else return o1.getB().toString().compareTo(o2.getB().toString());
            }
        });
        Map<RouterBean, Pair<RouterBean, LinkBean>> p = new HashMap<>(N);
        Map<RouterBean, Float> d = new HashMap<>(N);

        // initialize
        logger.trace("Dijkstra: init");
        for (RouterBean r : DirectedGraphBean.getVertices(Integer.MAX_VALUE)) {
            d.put(r, Float.MAX_VALUE);
        }
        d.put(v1, 0.0f);
        p.put(v1, null);
        q.add(new Pair<>(0.0f, v1));

        
        // Get the ball rolling!!!
        logger.trace("Dijkstra: started");
        while (!q.isEmpty() && d.get(v2)==Float.MAX_VALUE) {
            Pair<Float, RouterBean> pair = q.iterator().next();
            q.remove(pair);
            Float dv = pair.getA();
            RouterBean v = pair.getB();
            List<LinkBean> incidentVertices = DirectedGraphBean.getIncidentVertices(v, minBandwidth);
            if(!incidentVertices.isEmpty()) {
                Iterator<LinkBean> iter = incidentVertices.iterator();
                while(iter.hasNext()) {
                    LinkBean l = iter.next();
                    if(l.getCurrentBandwidth()<minBandwidth) continue;
                    RouterBean w = l.getRouter1();
                    if(l.getRouter1().equals(v)) w = l.getRouter2();
                    if(d.get(w) > dv + 1/l.getBandwidth()) {
                        if(d.get(w)!=Float.MAX_VALUE)
                            q.remove(new Pair<>(d.get(w), w));
                        d.put(w, d.get(v)+1/l.getBandwidth());
                        q.add(new Pair<>(d.get(w), w));
                        p.put(w, new Pair<>(v, l));
                    }
                }
            }
        }

        // Perform counter motion (reverse)
        RouterBean r = v2;
        while(r!=null && !r.equals(v1)) {
            if(p.get(r)!=null) {
                //circuit.addEdge(r, p.get(r).getA(), p.get(r).getB());
                circuit.add(p.get(r).getB());
                r = p.get(r).getA();
            } else r = null;
        }
        
        p.clear();
        q.clear();
        
        if(r==null) {
            circuit.clear();
            circuit = null;
        }
        
        return circuit;
    }
    
    public static List<LinkBean> 
            bfs(RouterBean v1,
                     RouterBean v2,
                     float minBandwidth
                     ) 
    {
        logger.trace("Starting bfs("+ v1 + " and "+ v2 + ") with minBandwidth="+minBandwidth);
        int N = DirectedGraphBean.size();

        // create data structures
        logger.trace("bfs: creating data structures");
        List<LinkBean> circuit = new ArrayList<>();
        Deque<RouterBean> q = new LinkedList<>();
        Map<RouterBean, Pair<RouterBean, LinkBean>> p = new HashMap<>(N);

        // initialize
        logger.trace("bfs: init");
        p.put(v1, null);
        q.add(v1);

        // Get the ball rolling!!!
        logger.trace("bfs: started");
        while (!q.isEmpty() && p.get(v2)==null) {
            RouterBean v = q.poll();
            List<LinkBean> incidentVertices = DirectedGraphBean.getIncidentVertices(v, minBandwidth);
            if(!incidentVertices.isEmpty()) {
                Iterator<LinkBean> iter = incidentVertices.iterator();
                while(iter.hasNext()) {
                    LinkBean l = iter.next();
                    if(l.getCurrentBandwidth()<minBandwidth) continue;
                    RouterBean w = l.getRouter1();
                    if(l.getRouter1().equals(v)) w = l.getRouter2();
                    if(p.get(w)!=null) continue;
                    q.addLast(w);
                    p.put(w, new Pair<>(v, l));
                }
            }
        }

        // Perform counter motion (reverse)
        RouterBean r = v2;
        while(r!=null && !r.equals(v1)) {
            if(p.get(r)!=null) {
                //circuit.addEdge(r, p.get(r).getA(), p.get(r).getB());
                circuit.add(p.get(r).getB());
                r = p.get(r).getA();
            } else r = null;
        }
        
        p.clear();
        q.clear();
        
        if(r==null) {
            circuit.clear();
            circuit = null;
        }
        return circuit;
    }
}